1. Field of the Invention
The present invention relates generally to a method and arrangement of ascertaining error locations and the corresponding error patterns of a decoded code word(s) in a digital data communications system, and more specifically to such a method and arrangement using a so-called Chien's searching algorithm.
2. Description of Prior Art
Before turning to the present invention it is deemed advantageous to briefly discuss prior art with reference to FIGS. 1 and 2.
FIG. 1 is a block diagram schematically showing an overall error correcting arrangement which follows a suitable decoder such as a Viterbi decoder.
Code words, outputted from the above mentioned decoder, are successively applied to a syndrome calculator 10 and a memory 12. The memory 12 is to delay the code words applied thereto by a predetermined time period in order to compensate for delay of the code words induced while processed by blocks 10, 14, 16 and 18.
The syndrome calculator 10 produces syndromes from the code words applied thereto. A polynomial generator 14 is provided to issue two polynomials: one is an error-locator polynomial and the other is an error numerical value polynomial. These two polynomials wall will be given later.
The aforesaid two polynomials, obtained at the block 14, are applied to the next stage, viz., an error location and error pattern determiner 16 which is directly concerned with the present invention.
The block 16 generates error location data and error pattern data which are applied to an error corrector 20 via an error data check circuit 18. The error corrector 20 implements error correction included in the code words applied thereto from the memory 12 using the error location data and the error pattern applied thereto from the data check circuit 18. Thus, error corrected code words can be derived from the error corrector 20.
The above mentioned error correction using the syndrome scheme is well known in the art. For further details reference should be made to a book entitled "Error Control Coding" by Shu Lin, et al., published 1983 by Prentice-Hall, Inc. Englewood Cliffs, N.J. 07632, merely by way of example.
As is known in the art, a so-called Chien's searching algorithm has proven suited for error correction of code words in Galois field GF(2.sup.m) (m is a positive integer). In more specific terms, the Chien's searching algorithm is to determine error locations and the corresponding error patterns using an error-locator polynomial (depicted by .sigma.(X)) and an error numerical value polynomial (depicted by p(X)) both derived from Euclid's algorithm. The root of .sigma.(X)=0 indicates an error location. Therefore, let .alpha. be a primitive element in GF(2.sup.m). Briefly speaking, the Chien's searching circuit is arranged such as to successively replace "X" with .alpha..sup.0, .alpha..sup.-1, .alpha..sup.-2, . . . and check to see if outputs of an exclusive-or thereof assume zeros.
FIG. 2 is a block diagram schematically showing a known Chien's searching circuit which determines error locations and the corresponding error patterns of the code words applied thereto. The error location polynomial .sigma.(X) and the error numerical value polynomial p(x) are respectively given by EQU .sigma.(X)=.sigma..sub.t X.sup.t +.sigma..sub.t-1 X.sup.t-1 +. . . +.sigma..sub.2 X.sup.2 +.sigma..sub.1 X+.sigma..sub.0 ( 1) EQU p(X)=p.sub.t-1 X.sup.t-1 +. . . +p.sub.2 X.sup.2 +p.sub.1 X.sup.1 +p.sub.0( 2)
Further, the number of the maximum correctable symbols is denoted by "t".
In the present disclosure, term "symbol" implies a component which forms part of a code word. In other words, a code word consists of a plurality of symbols each of which has a predetermined bit length.
In FIG. 2, error location data (.alpha..sup.-1)(i=0, 1, 2, . . . ) is obtained using the following blocks: registers Rl-Rt, selectors S1-St, multipliers M1-Mt, an exclusive-or gate E1, an all-zero detector 30, a power index counter 31 and a index-vector converter 32. It is assumed, merely for the sake of simplifying the descriptions, that the multipliers M1, M2, . . . , M(t-1), and Mt are respectively provided with registers (not shown) for storing .alpha..sup.-1, .alpha..sup.-2, . . . , .alpha..sup.1-t, and .alpha..sup.-t.
On the other hand, the arrangement for obtaining the corresponding error pattern data (e.sub.i) includes, two exclusive-or gates E2 und E3, multipliers MA0-MA(t-1) and MB0-MB(t-1), and an error pattern calculator 34, in addition to the above mentioned blocks R1-Rt, S1-St, and M1-Mt. As in the above, it is assumed that the multipliers MA0, MA1, MA2, . . . , and MA(t-1) are respectively provided with register (not shown) for storing .sigma..sub.0.sup.-1, .sigma..sub.1.sup.-1, .sigma..sub.2.sup.-1, . . . , and .sigma..sub.t-1.sup.-I. In the similar manner, it is assumed that he multipliers MB0, MB1, MB2, . . . , and MB(t-1) are respectively provided with registers (not shown) for storing p.sub.0, p.sub.1, p.sub.2, . . . , p.sub.t-1.
Prior to initiating the operations of the FIG. 2 arrangement, the multipliers M1, M2, . . . , M(t-1), and Mt store respectively .alpha..sup.-1, .alpha..sup.-2, . . . , .alpha..sup.l-t and .alpha..sup.-t in the corresponding registers (not shown) thereof. Further, the multipliers MA0, MA1, MA2, . . . , and MA(t-1) store respectively .sigma..sub.0.sup.-1, .sigma..sub.1.sup.-1, .sigma..sub.2.sup.-1, . . . , and .sigma..sub.t-1.sup.-1 in the corresponding registers (not shown) thereof. Similarly, the multipliers MB0, MB1, MB2, . . . , and MB(t-1) store respectively P0, P1, P2, . . . , P.sub.t-1 within the corresponding registers (not shown) thereof.
Firstly, in order to replace X of Equation (1) with .alpha..sup.0 (viz., i=0), the coefficients .sigma..sub.0, .sigma..sub.1, .sigma..sub.2, . . . , .sigma..sub.t-1, and .sigma..sub.t are applied to the arrangement of FIG. 2 from the polynomial generator 14. In more specific terms, .sigma..sub.0 is directly applied to the exclusive-or gate E1, while .sigma..sub.1, .sigma..sub.2, . . . , .sigma..sub.t-1, and .sigma..sub.t are respectively applied to the exclusive-or gate E1 via the selectors S1, S2, . . . , S(t-1), and St. That is to say, when i=0, each of selector S1-St selects the coefficients applied thereto from the generator 14.
The gate E1 implements exclusive-or operations of the corresponding bits of the coefficients .sigma..sub.o, .sigma..sub.1, .sigma..sub.2, . . . , .sigma..sub.t-1, and .sigma..sub.t. The outputs of the exclusive-or gate E1 are applied to the all-zero detector 30. It is assumed for a better understanding that each of the coefficients .sigma..sub.0, .sigma..sub.1, .sigma..sub.2, . . . , .sigma..sub.t-1, and .sigma..sub.t has a bit length of eight. In such a case, the gate E1 carries out eight exclusive-or operations at the same time. More specifically, if
.sigma..sub.0 =0000 0000 PA1 .sigma..sub.1 =0000 0000 PA1 .sigma..sub.2 =0000 0000 PA1 .sigma..sub.t-1 =0000 0000 PA1 .sigma..sub.t =0000 0000
****
then the eight outputs of the exclusive-or gate E1 exhibit all "0"s. Thus, the detector 30 detects this situation which is applied to the index-vector converter 32 and the power index counter 31. More specifically, before the arrangement of FIG. 2 starts the operation thereof, the counter 31 is reset such that the power index "i" of .alpha..sup.-i indicates "+1". Thereafter, the counter 31 decrements the power index "i" by one each time the exclusive or gate E1 issues its output. In the above-mentioned initial stage (cycle), the counter 31 applies .alpha..sup.0 to the error pattern calculator 34.
While the exclusive-or gate E1 implements the above mentioned operations, the multipliers M1, M2, . . . , M(t-1), and Mt multiplication respectively the output of the selectors S1, S2, . . . , S(t-1), and St by .alpha..sup.-1, .alpha..sup.-2, . . . , .alpha..sup.l-t and .alpha..sup.-t. The multiplication results .sigma..sub.1 .alpha..sup.-1, .sigma..sub.2 .alpha..sup.-2, . . . , .sigma..sub.t-1 .alpha..sup.1-t and .sigma..sub.t .alpha..sup.-t are respectively latched by the registers R1, R2, . . . , R(t-1), and Rt.
Following this, in order to replace X of Equation (1) with .alpha..sup.1 (viz., i=1), .sigma..sub.0 is directly applied to the exclusive-or gate E1 as in the, above case. However, the selectors S1, S2, . . . , S(t-1), and St, in turn, selects the corresponding contents stored in the registers R1, R2, . . . , R(t-1), and Rt. Accordingly, the exclusive-or gate E1 is supplied within .sigma..sub.0, .sigma..sub.1 .alpha..sup.-1, .sigma..sub.2 .alpha..sup.-2, . . . , .sigma..sub.t-1 .alpha..sup.l-t, and .sigma..sub.t .alpha..sup.-t. Thereafter, the same operations as mentioned above are implemented at the gate El. In the event that the detector 30 detects all "0"s of the results issued from the exclusive-or gate E1 the power index counter 31 issues .alpha..sup.-1 which indicates an error location.
Furthermore, in order to replace X of Equation (1) with .alpha..sup.2 (viz., i=2), .sigma..sub.0, is directly applied to the exclusive-or gate E1. As in the case of i=1, the selectors S1, S2, . . . , S(t-1), and St select the corresponding contents stored in the registers R1, R2, . . . , R(t-1) and Rt, respectively. Accordingly, the exclusive-or gate E1 is supplied with .sigma..sub.0, .sigma..sub.1 .alpha..sup.-2, .sigma..sub.2 .alpha..sup.-4, . . . , .sigma..sub.t-1 .alpha..sup.2-2t, and .sigma..sub.t .alpha..sup.-2t. Thereafter, the same operations as mentioned in the above two cases are implemented thereat.
These operations are iterated until i=n wherein it is readily understood that .sigma..sub.0, .sigma..sub.1 .alpha..sup.-n, .sigma..sub.2 .alpha..sup.-2n, . . . , .sigma..sub.t-1 .alpha..sup.n-tn, and .sigma..sub.t .alpha..sup.-tn are applied to the exclusive-or gate E1.
An error location is defined as an index .alpha..sup.-1 (.sigma.(.alpha..sup.-i) =0) which is applied to the index-vector converter 32 and is then converted into the corresponding vector. The vector thus obtained is applied to the next stage, viz., the error data check circuit 18 (FIG. 1). The index-vector converter 32 is required to have a lookup-table (not shown) previously stored in a ROM (Read Only Memory) for the index-vector conversion.
As is well known in the art, a primitive polynomial f(X) over GF(2.sup.8) is given by EQU f(X)=X.sup.8 +X.sup.4 +X.sup.3 +X.sup.2 +1 (3)
Therefore, the index-vector pairs (viz., table of Galois Field GF(2.sup.8)) stored in the ROM are
______________________________________ -- = 0000 0000 .alpha..sup.0 = 1000 0000 .alpha..sup.1 = 0100 0000 .alpha..sup.2 = 0010 0000 .alpha..sup.3 = 0000 1000 . . . . . . .alpha..sup.125 = 1100 1100 .alpha..sup.126 = 0110 0110 .alpha..sup.127 = 0011 0011 .alpha..sup.128 = 1010 0001 . . . . . . .alpha..sup.251 = 0001 1011 .alpha..sup.252 = 1011 0101 .alpha..sup.253 = 1110 0010 .alpha..sup.254 = 0111 0001 ______________________________________
That is, the above mentioned index-vector conversion requires 256 index-vector pairs stored in the ROM. Further, if GF(2.sup.10) is used, then the index-vector pairs amount to a very large number of 1024. The tables of Galois Fields are shown in APPENDIX A of the aforesaid reference book.
When the error location .alpha..sup.-1 (.sigma.(.alpha..sup.-1)=0) is ascertained, the error pattern calculator 34 acquires the outputs of the counter 31 and the exclusive-or gates E2 and E3 in order to obtain the corresponding error pattern e.sub.i. The error pattern e.sub.i is given by EQU e.sub.i =p(X)/[.sigma.'(X).multidot.X] (4)
When error location .alpha..sup.-i (viz., .sigma.(.alpha..sup.-i)=0) is defined, the corresponding error pattern is determined by substituting X for .alpha..sup.-i and is implemented by the hardware arrangement which includes the exclusive-or gates E2 and E3, the multipliers MA0-MA(t-1) and MB0-MB(t-1), and the error pattern calculator 34.
The numerator p(.alpha..sup.-i) of Equation (4) is calculated as follows. The multiplier MA0, MA1, MA2, . . . , MA(t-1) multiply .sigma..sub.0, .sigma..sub.1 .alpha..sup.-i, .sigma..sub.2 .alpha..sup.-2i, . . . , .sigma..sub.t-1 .alpha..sup.i-ti by the reciprocals of the coefficients of Equation (2), viz., .sigma..sub.0.sup.-1, .sigma..sub.1.sup.-1, .sigma..sub.2.sup.-1, . . . , .sigma..sub.t-1.sup.-1, respectively. Thereafter, the following multipliers MB0, MB1, MB2, . . . , MB(t-1) multiply the outputs of the preceding multipliers MA0, MA1, MA2, . . . , MA(t-1) by p.sub.0, p.sub.1, p.sub.2, . . . , p.sub.t-1, respectively. Thus, the multiplication results p.sub.0, p.sub.1 .alpha..sup.-n, p.sub.2 .alpha..sup.-2n, . . . , p.sub.t-1 .alpha..sup.n-tn are applied to the exclusive-or gate E3. This gate E3 implements the exclusive-or operations of the corresponding bits of each of the above mentioned multiplication results as in the gate E1. The output of the exclusive-or gate E3 is applied to the error pattern calculator 34.
The denominator [.sigma.'(X).multidot.X] of Equation (4) is calculated as follows. The exclusive-or gate E2 receives the selector's outputs wherein each of the suffixes of .sigma. exhibits an odd number. That is, the exclusive-or gate E2 receives .sigma..sub.1 .alpha..sup.-n, .sigma..sub.3 .alpha..sup.-3n, . . . , .sigma..sub.t-3 .alpha..sup.-(t-3)n, .sigma..sub.t-1 .alpha..sup.-(t-1)n which are respectively generated from the selectors S1, S3, . . . , S(t-3) and S(t-1) (although the selectors S3 and S(t-3) are not shown in FIG. 2).
The error pattern calculator 34 is supplied with the outputs of the counter 31 and the exclusive-or gates E2 and E3, and outputs the error pattern e.sub.i after executing the following divisional operation: EQU e.sub.i =p(.alpha..sup.-i)/[.sigma.'(.alpha..sup.-i).multidot..alpha..sup.-i ]
The above mentioned known Chien's searching, however, has suffered from the drawbacks that the index .alpha..sup.-i (.sigma.(.alpha..sup.-i)=0) should be converted into the corresponding vector using a large lookup table stored in a ROM. As discussed above, if GF(2.sup.8) then the number of the index-vector pairs amounts to 255, while if GF(2.sup.10) then the number of the index-vector pairs amounts to 1024. In addition to this problem, the error data check circuit 18 (FIG. 1) is undesirably required to define the error location using the vector applied thereto from the Chien's searching circuit.
Still further, with the prior art, determining the error pattern data requires the reciprocals of the coefficients of the error-location polynomial. These reciprocal are usually obtained using a table stored in a ROM (not shown in FIG. 2). Further, the two multiplying circuits (MA0-MA(t-1) and MB-MB(t-1)) are required which inevitably require a plurality of registers for temporarily storing intermediate values. These complex circuitry renders it difficult to fabricate the arrangement of FIG. 2 by LSI (Large Sale Integration) techniques.